NCi là lớp các bài toán quyết định được bởi các mạch logic đồng dạng có chiều sâu O ( log i ⁡ n ) {\displaystyle O(\log ^{i}n)} và kích thước đa thức. Ta có

NC 1 ⊆ NC 2 ⊆ ⋯ ⊆ NC i ⊆ ⋯ NC {\displaystyle {\textbf {NC}}^{1}\subseteq {\textbf {NC}}^{2}\subseteq \cdots \subseteq {\textbf {NC}}^{i}\subseteq \cdots {\textbf {NC}}}

Đây gọi là cấp bậc NC.

Ta có thể so sánh lớp NC với lớp L và NL. Theo Papadimitriou (1993)Lỗi harv: không có mục tiêu: CITEREFPapadimitriou1993 (trợ giúp), định lý 16.1:

N C 1 ⊆ L ⊆ N L ⊆ N C 2 ⊆ P . {\displaystyle \mathbf {NC} ^{1}\subseteq \mathbf {L} \subseteq \mathbf {NL} \subseteq \mathbf {NC} ^{2}\subseteq \mathbf {P} .}

Tương tự như vậy, NC tương đương với các bài toán giải được bằng máy Turing luân phiên với bộ nhớ O ( log ⁡ n ) {\displaystyle O(\log n)} và ( log ⁡ n ) O ( 1 ) {\displaystyle (\log n)^{O(1)}} lần luân phiên.[2]

Vấn đề mở: các lớp trong cấp bậc NC có khác nhau?

Một vấn đề mở trong lý thuyết độ phức tạp tính toán là các lớp trong cấp bậc NC có khác nhau. Papadimitriou đã nhận thấy rằng, nếu NCi = NCi+1 với một số i nào đó, thì NCi = NCj với mọi j ≥ i, và do đó, NCi = NC. Nhận xét này gọi là sự sụp đổ của cấp bậc NC bởi chỉ cần hai lớp bằng nhau trong

NC 1 ⊆ NC 2 ⊆ ⋯ {\displaystyle {\textbf {NC}}^{1}\subseteq {\textbf {NC}}^{2}\subseteq \cdots }

thì toàn bộ cấp bậc NC "sụp đổ" xuống một tầng thứ i nào đó.